# 拼接最大数： https://leetcode-cn.com/problems/create-maximum-number/

class Solution:
    def maxNumber(self, nums1: list, nums2: list, k: int) -> list:
        """
            抓住核心，因为要从每个数组取出来的元素是要保证相对顺序的，所以模拟这个过程就是：
            1. 从每个数组中去取部分数，数的和是 k个， 比如 k 是5 那么可能， (1, 4), (2, 3), (0, 5)等，代表数组中各取几个
            2. 把这些数拼接成一个数
            3. 暴力：要列举所有的可能，从两个数组中取数字个数，比较那种 算出来的数最大
        """
        # 定义功能函数
        def maxSubSequence(nums: list, leg: int) -> list:
            """ 选取leg个数,最大子序列 
                设想一下，最大子序列代表的是一个数字，那么肯定优先考虑高位数字最大，这样一来，假如取4位，千百十个。
                这就维系成了一个 递减栈，1. 当元素递减入栈， 2.当元素大于栈内元素，循环判断，然后出栈（要注意，该元素后面一定要不小于总位数的）
            """
            # 单调栈
            stack = list()
            n = len(nums)
            for i in range(n):
                while stack and nums[i] > stack[-1] and len(stack) + n - i > leg:
                    stack.pop()
                if len(stack) < leg: stack.append(nums[i])
            
            # python的恰好是列表，直接返回
            return stack

        def combine(l1: list, l2: list) -> list:
            """ 合并两个数组 
                有点类似归并排序那种合并操作，两个数组比较，大的放前面，最后谁剩下，添加到尾部
                注意点： [6, 7] [6, 0, 4] ， 这时候，6 相同的情况下，要谁的6就有窍门了， 如果先要 第二个的6，那么会是 66704, 显然先要第一个的6， 67604 才是最大的。
                方法： 当两个元素相等时， 一直往后比较，谁的后位大，先添加谁，直到最后一位都相等的话，那就加谁都行 
            """
            n, m = len(l1), len(l2)
            i = j = 0  
            if n == 0: return l2
            if m == 0: return l1
            rst = [0] * (n + m)
            # 直接遍历 n + m 次，将结果都加进去
            for k in range(n + m):
                # 大于0说明 l1大
                if SubCompare(l1, i, l2, j) > 0:
                    rst[k] = l1[i]
                    i += 1
                else:
                    rst[k] = l2[j]
                    j += 1

            return rst
        
        # 再定义一个比较函数，用来确定 合并函数中，那个子序列元素先拼接
        def SubCompare(l1: list, i: int, l2: list, j: int) -> bool:
            ip, jp = i, j
            n, m = len(l1), len(l2)
            while  ip < n and jp < m:
                diff = l1[ip] - l2[jp]
                if diff != 0: return diff
                ip += 1
                jp += 1
            
            # 循环结束，说明都相等，那谁长就先添加谁, 看谁剩下长度长
            return (n - ip) - (m - jp)

  
        def compare(rst: list, f: list) -> list:
            """ 比较大小, 直接按位比较即可, 如果rst > f 对应位元素，就返回True，证明rst大 """
            n = len(rst)
            for i in range(n):
                if rst[i] > f[i]:
                    return True
                elif rst[i] < f[i]:
                    return False

        m, n = len(nums1), len(nums2)
        # 1. 首先需要判断一下两个数中各需要抽多少数, 因为不确定哪个子序列短，并且 K 的值。所以这里 分析出来也是难点
        start = max(0, k - n)
        end  = min(m, k)
        
        # 2. 遍历所有可能组合
        rst = [0] * k
        for leg in range(start, end + 1): # end + 1 range循环才能取到end
            # 3.定义获取 leg 长度的数组
            l1 = maxSubSequence(nums1, leg)
            l2 = maxSubSequence(nums2, k - leg)
            # 4. 然后合并这两个数组，变为表示一个最大数字的
            finalList = combine(l1, l2)
            # 5. 比较出最大的
            if not compare(rst, finalList): rst = finalList

        # 6. 返回最大数组
        return rst
